package done.easy_101_200;

import com.study.common.ListNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 141. Linked List Cycle 给定一个链表，判断链表中是否有环。
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置
 * （索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * <p>
 * 示例 1：
 * 输入：head = [3, 2, 0, -4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 * @author wangxiaozhe
 */
@Slf4j
public class LinkedListCycle {

    @SuppressWarnings("all")
    public boolean hasCycle(ListNode head) {
        // 190325 first
        // 190405 second
        // 190528 third
        // 190605 fourth
        return false;
    }

    @Test
    public void test() {
        ListNode first = ListNode.newCycle(3, 2, 0, -4, 2);
        info(hasCycle(first));
    }
}
































/*
// 方法一 快慢指针
public boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast!=null || slow!=null) {
        if (fast.next!=null)
            fast = fast.next.next;

        slow = slow.next;
        if (fast == slow)
            return true;
    }
    return false;
}

// 方法二 set （不推荐）
public boolean hasCycle(ListNode head) {
    // Set的特点是不允许重复，并且有contains方法
    Set<ListNode> node = new HashSet<>();

    // 迭代整个链表
    while (head!=null) {

        // 查到重复节点 就直接返回
        if (node.contains(head)) {
            return true;

            // 没有查重就加到链表后面
        } else {
            node.add(head);
        }

        // 链表循环
        head = head.next;
    }
    return false;
}
*/
